package main

func getIntersectionNode(headA, headB *ListNode) *ListNode {
	if headA == nil || headB == nil {
		return nil
	}
	//构造等长链表
	tempA := headA
	a := 0
	for tempA != nil {
		a++
		tempA = tempA.Next
	}
	tempB := headB
	b := 0
	for tempB != nil {
		b++
		tempB = tempB.Next
	}
	tempA = headA
	tempB = headB
	for tempA != nil || tempB != nil {
		if tempA == nil {
			tempA = headB
		}
		if tempB == nil {
			tempB = headA
		}
		if tempA == tempB {
			return tempA
		}
		tempA = tempA.Next
		tempB = tempB.Next
	}
	return nil
}

func main() {
	n1 := &ListNode{Val: 4}
	n2 := &ListNode{Val: 1}
	n3 := &ListNode{Val: 8}
	n4 := &ListNode{Val: 4}
	n5 := &ListNode{Val: 5}
	n21 := &ListNode{Val: 5}
	n22 := &ListNode{Val: 0}
	n23 := &ListNode{Val: 1}
	n1.Next = n2
	n2.Next = n3
	n3.Next = n4
	n4.Next = n5
	n21.Next = n22
	n22.Next = n23
	n23.Next = n3
	node := getIntersectionNode(n1, n21)
	println(node.Val)
}
